/**
 * 0039
 *  
 * @Author : roryrywang
 * @DateTime : 2024/8/15 23:32
 */

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> res;

    void dfs(vector<int> &candidates, int target, int sum, int x) {
        if (sum == target) {
            res.push_back(tmp);
            return;
        }
        for (int i = x; i < candidates.size(); ++i) {
            if (candidates[i] + sum > target) {
                break;
            }
            tmp.push_back(candidates[i]);
            dfs(candidates, target, sum + candidates[i], i);
            tmp.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0, 0);
        return res;
    }
};

int main() {
    Solution sl;
    vector<int> candidates = {2, 3, 6, 7};
    int target = 7;
    for (vector<int> i: sl.combinationSum(candidates, target)) {
        for (int j: i) {
            printf("%d ", j);
        }
        printf("\n");
    }
    printf("\n");
    return 0;
}